// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-14 13:24
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import java.util.ArrayList;
import java.util.HashMap;

public class FindRestaurant {
    /**
     * 获取最小公共子字符串索引
     */
    public String[] findRestaurant(String[] list1, String[] list2) {
        // 朴素解法 -> 时间复杂度为O(m + n) -> Hash匹配
        int n = list1.length, m = list2.length, min = Integer.MAX_VALUE, tmp = 0;
        ArrayList<String> ans = new ArrayList<>();
        /*
         * 店名 + 索引下标
         */
        HashMap<String, Integer> words = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Integer index = words.getOrDefault(list1[i], i);
            if (index <= i) {
                words.put(list1[i], index);
            }
        }
        for (int i = 0; i < m; i++) {
            if (words.containsKey(list2[i])) {
                tmp = words.get(list2[i]) + i;
                if (tmp < min) {
                    min = tmp;
                    ans.clear();
                    ans.add(list2[i]);
                } else if (tmp == min) {
                    ans.add(list2[i]);
                }
            }
        }

        System.out.println(ans);
        return ans.toArray(new String[ans.size()]);
    }
}
